package arithmetic.LeetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import org.junit.jupiter.api.Test;

/**
 * 39. 组合总和
 * 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
 * candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
 * <p>
 * 对于给定的输入，保证和为 target 的不同组合数少于 150 个。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * 输入：candidates = [2,3,6,7], target = 7
 * 输出：[[2,2,3],[7]]
 * 解释：
 * 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
 * 7 也是一个候选， 7 = 7 。
 * 仅有这两种组合。
 * <p>
 * 示例 2：
 * 输入: candidates = [2,3,5], target = 8
 * 输出: [[2,2,2,2],[2,3,3],[3,5]]
 * 示例 3：
 * <p>
 * 输入: candidates = [2], target = 1
 * 输出: []
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= candidates.length <= 30
 * 1 <= candidates[i] <= 200
 * candidate 中的每个元素都 互不相同
 * 1 <= target <= 500
 * <p>
 * https://leetcode.cn/problems/combination-sum/
 *
 * @author jiangfeng on 2022/6/21
 */
public class CombinationSum {

    @Test
    public void test() {

        System.out.println(combinationSum(new int[] {2, 3, 6, 7}, 7));
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        // 组合不同
        Arrays.sort(candidates);
        // 遍历搜索,每一次都有选A和不选A,
        // 2. 如何避免重复,按序号来.?
        if (target < candidates[0]) {
            return Collections.emptyList();
        }
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        // 两种剪枝方法. 1. target 一个一个减,(避免重复搜索)  2. 每个元素都有选和不选,
        sum(candidates, target, 0, temp, res);
        return res;
    }

    public void sum(int[] candidates, int target, int index, List<Integer> temp, List<List<Integer>> res) {
        if (target < 0) {
            return;
        }

        for (int i = index; i < candidates.length; i++) {
            // 后面的元素更大了
            if (candidates[i] > target) {
                //temp = new ArrayList<>();
                return;
            }
            temp.add(candidates[i]);
            if (target == candidates[i]) {

                res.add(new ArrayList<>(temp));
                //temp = new ArrayList<>();
                return;
            }
            sum(candidates, target - candidates[i], i, temp, res);
            // 归位
            temp.remove(temp.size() - 1);
        }

    }



}


class Solution1 {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        boolean[] step = new boolean[nums.length];
        List<List<Integer>>  res = new ArrayList<>();
        Arrays.sort(nums);
        sub(nums,step,0,true,res);
        sub(nums,step,0,false,res);
        return res;
    }
    public void sub(int[] nums,boolean[] step,int j,boolean select, List<List<Integer>>  res) {
        if(j==nums.length){
            return;
        }
        // 减枝: 如果上一个元素没选,且和当前元素一样,则跳过
        // if(j>1 && !select && nums[j-1]==nums[j]){ 错了 这个本个元素
        if(j>1 && !step[j-1] && nums[j-1]==nums[j]){
            return ;
        }
        step[j] = select;
        if(j<nums.length -1){
            sub(nums,step,j+1,true,res);
            sub(nums,step,j+1,false,res);
            return;
        }
        List<Integer> temp = new ArrayList<>();
        for(int i =0;i<nums.length;i++){

            if(step[i]){
                temp.add(nums[i]);
            }

        }
        res.add(temp);
    }
}
